package main

import "fmt"

func searchInsert(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	if target < nums[left] {
		return 0
	}
	if target > nums[right] {
		return len(nums)
	}
	for left != right {
		if right-left == 1 {
			if target == nums[left] {
				return left
			}
			if target == nums[right] {
				return right
			}
			if target > nums[left] && target < nums[right] {
				return right
			}
		}
		if nums[(left+right)/2] > target {
			right = (left + right) / 2
		} else if nums[(left+right)/2] < target {
			left = (left + right) / 2
		} else {
			return (left + right) / 2
		}
	}
	return 0
}

func main() {
	ii := []int{-1}
	insert := searchInsert(ii, -1)
	fmt.Println(insert)
}
